Functional Programming for Dynamic and Large Data with Self-Adjusting Computation
Identifieur interne : 000183 ( France/Analysis ); précédent : 000182; suivant : 000184Functional Programming for Dynamic and Large Data with Self-Adjusting Computation
Auteurs : Yan Chen [France, Allemagne] ; Umut A. Acar [France] ; Kanat Tangwongsan [Inde]Source :
English descriptors
- mix :
Abstract
Combining type theory, language design, and empirical work, we present techniques for computing with large and dynamically changing datasets. Based on lambda calculus, our techniques are suitable for expressing a diverse set of algorithms on large datasets and, via self-adjusting computation, enable computations to respond automatically to changes in their data. To improve the scalability of self-adjusting computation, we present a type system for precise dependency tracking that minimizes the time and space for storing dependency metadata. The type system eliminates an important assumption of prior work that can lead to recording spurious dependencies. We present a type-directed translation algorithm that generates correct self-adjusting programs without relying on this assumption. We then show a probabilistic-chunking technique to further decrease space usage by controlling the fundamental space-time tradeoff in self-adjusting computation. We implement and evaluate these techniques, showing promising results on challenging benchmarks involving large graphs.
Url:
DOI: 10.1145/2628136.2628150
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000293
- to stream Hal, to step Curation: 000293
- to stream Hal, to step Checkpoint: 000205
- to stream Main, to step Merge: 000695
- to stream Main, to step Curation: 000695
- to stream Main, to step Exploration: 000695
- to stream France, to step Extraction: 000183
Links to Exploration step
Hal:hal-01100337Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Functional Programming for Dynamic and Large Data with Self-Adjusting Computation</title><author><name sortKey="Chen, Yan" sort="Chen, Yan" uniqKey="Chen Y" first="Yan" last="Chen">Yan Chen</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-105111" status="VALID"> <orgName>Max Planck Institute for Software Systems</orgName> <orgName type="acronym">MPI Software systems</orgName> <desc> <address> <addrLine>Max Planck Institute for Software Systems Wartburg Martin-Luther-Straße 12 D-66111 Saarbrücken Germany</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.mpi-sws.org/index_noflash.php?n=contact</ref> </desc> <listRelation> <relation active="#struct-300044" type="direct"></relation> </listRelation> <tutelles><tutelle active="#struct-300044" type="direct"><org type="institution" xml:id="struct-300044" status="VALID"> <orgName>Max-Planck-Institut</orgName> <desc> <address> <country key="DE"></country> </address> </desc> </org></tutelle></tutelles></hal:affiliation><country>France</country><country>Allemagne</country><orgName type="university">Société Max-Planck</orgName></affiliation></author><author><name sortKey="Acar, Umut A" sort="Acar, Umut A" uniqKey="Acar U" first="Umut A." last="Acar">Umut A. Acar</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD"> <orgName>Programming languages, types, compilation and proofs</orgName> <orgName type="acronym">GALLIUM</orgName> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/gallium</ref> </desc> <listRelation> <relation active="#struct-86790" type="direct"></relation> <relation active="#struct-300009" type="indirect"></relation> </listRelation> <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID"> <idno type="RNSR">196718247G</idno> <orgName>Inria Paris-Rocquencourt</orgName> <desc> <address> <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Tangwongsan, Kanat" sort="Tangwongsan, Kanat" uniqKey="Tangwongsan K" first="Kanat" last="Tangwongsan">Kanat Tangwongsan</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-409801" status="INCOMING"> <orgName>Mahidol University International College</orgName> <desc> <address> <country key="IN"></country> </address> </desc> </hal:affiliation><country>Inde</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01100337</idno><idno type="halId">hal-01100337</idno><idno type="halUri">https://hal.inria.fr/hal-01100337</idno><idno type="url">https://hal.inria.fr/hal-01100337</idno><idno type="doi">10.1145/2628136.2628150</idno><date when="2014-09-01">2014-09-01</date><idno type="wicri:Area/Hal/Corpus">000293</idno><idno type="wicri:Area/Hal/Curation">000293</idno><idno type="wicri:Area/Hal/Checkpoint">000205</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000205</idno><idno type="wicri:Area/Main/Merge">000695</idno><idno type="wicri:Area/Main/Curation">000695</idno><idno type="wicri:Area/Main/Exploration">000695</idno><idno type="wicri:Area/France/Extraction">000183</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Functional Programming for Dynamic and Large Data with Self-Adjusting Computation</title><author><name sortKey="Chen, Yan" sort="Chen, Yan" uniqKey="Chen Y" first="Yan" last="Chen">Yan Chen</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-105111" status="VALID"> <orgName>Max Planck Institute for Software Systems</orgName> <orgName type="acronym">MPI Software systems</orgName> <desc> <address> <addrLine>Max Planck Institute for Software Systems Wartburg Martin-Luther-Straße 12 D-66111 Saarbrücken Germany</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.mpi-sws.org/index_noflash.php?n=contact</ref> </desc> <listRelation> <relation active="#struct-300044" type="direct"></relation> </listRelation> <tutelles><tutelle active="#struct-300044" type="direct"><org type="institution" xml:id="struct-300044" status="VALID"> <orgName>Max-Planck-Institut</orgName> <desc> <address> <country key="DE"></country> </address> </desc> </org></tutelle></tutelles></hal:affiliation><country>France</country><country>Allemagne</country><orgName type="university">Société Max-Planck</orgName></affiliation></author><author><name sortKey="Acar, Umut A" sort="Acar, Umut A" uniqKey="Acar U" first="Umut A." last="Acar">Umut A. Acar</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-454410" status="OLD"> <orgName>Programming languages, types, compilation and proofs</orgName> <orgName type="acronym">GALLIUM</orgName> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/equipes/gallium</ref> </desc> <listRelation> <relation active="#struct-86790" type="direct"></relation> <relation active="#struct-300009" type="indirect"></relation> </listRelation> <tutelles><tutelle active="#struct-86790" type="direct"><org type="laboratory" xml:id="struct-86790" status="VALID"> <idno type="RNSR">196718247G</idno> <orgName>Inria Paris-Rocquencourt</orgName> <desc> <address> <addrLine>INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex / INRIA Paris - 23 avenue d'Italie 75013 Paris</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/paris-rocquencourt</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Tangwongsan, Kanat" sort="Tangwongsan, Kanat" uniqKey="Tangwongsan K" first="Kanat" last="Tangwongsan">Kanat Tangwongsan</name><affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-409801" status="INCOMING"> <orgName>Mahidol University International College</orgName> <desc> <address> <country key="IN"></country> </address> </desc> </hal:affiliation><country>Inde</country></affiliation></author></analytic><idno type="DOI">10.1145/2628136.2628150</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Granularity control</term><term>Incremental graph algorithms</term><term>Information-flow type system</term><term>Performance</term><term>Self-adjusting computation</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Combining type theory, language design, and empirical work, we present techniques for computing with large and dynamically changing datasets. Based on lambda calculus, our techniques are suitable for expressing a diverse set of algorithms on large datasets and, via self-adjusting computation, enable computations to respond automatically to changes in their data. To improve the scalability of self-adjusting computation, we present a type system for precise dependency tracking that minimizes the time and space for storing dependency metadata. The type system eliminates an important assumption of prior work that can lead to recording spurious dependencies. We present a type-directed translation algorithm that generates correct self-adjusting programs without relying on this assumption. We then show a probabilistic-chunking technique to further decrease space usage by controlling the fundamental space-time tradeoff in self-adjusting computation. We implement and evaluate these techniques, showing promising results on challenging benchmarks involving large graphs.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>France</li><li>Inde</li></country><orgName><li>Société Max-Planck</li></orgName></list><tree><country name="France"><noRegion><name sortKey="Chen, Yan" sort="Chen, Yan" uniqKey="Chen Y" first="Yan" last="Chen">Yan Chen</name></noRegion><name sortKey="Acar, Umut A" sort="Acar, Umut A" uniqKey="Acar U" first="Umut A." last="Acar">Umut A. Acar</name></country><country name="Inde"><noRegion><name sortKey="Tangwongsan, Kanat" sort="Tangwongsan, Kanat" uniqKey="Tangwongsan K" first="Kanat" last="Tangwongsan">Kanat Tangwongsan</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000183 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000183 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Amérique
|area= PittsburghV1
|flux= France
|étape= Analysis
|type= RBID
|clé= Hal:hal-01100337
|texte= Functional Programming for Dynamic and Large Data with Self-Adjusting Computation
}}
| This area was generated with Dilib version V0.6.38. |  |